#include <cassert>
#include <iostream>
#include <map>
#include <random>
#include <set>
#include <vector>
using namespace std;

template <typename Type, typename Com> class HeapGreater {
public:
  HeapGreater() : HeapSize(0) {}
  virtual ~HeapGreater() {}
  bool IsEmpty();
  int Size();
  bool Contains(const Type &node);
  bool Push(const Type &node);
  Type Get();
  void Pop();
  bool IsValid();

protected:
  void Heapyfy(unsigned int index);
  void HeapInsert(unsigned int index);
  inline unsigned int FatherPos(unsigned int pos) { return (pos - 1) >> 1; }
  inline unsigned int LeftKid(unsigned int pos) { return (pos << 1) + 1; }
  inline unsigned int RightKid(unsigned int pos) { return (pos << 1) + 2; }
  bool Swap(unsigned int a, unsigned int b);

private:
  vector<Type> BasicHeap;
  unsigned int HeapSize;
  map<Type, unsigned int, Com> BackIndex;
  Com Compter;
};

template <typename Type, typename Compare>
bool HeapGreater<Type, Compare>::Swap(unsigned int a, unsigned int b) {
  assert(a < HeapSize && b < HeapSize);

  BackIndex[BasicHeap[a]] = b;
  BackIndex[BasicHeap[b]] = a;

  Type c = BasicHeap[a];
  BasicHeap[a] = BasicHeap[b];
  BasicHeap[b] = c;
  return true;
}

template <typename Type, typename Compare>
void HeapGreater<Type, Compare>::HeapInsert(unsigned int index) {
  if (index >= HeapSize)
    return;
  if (index == 0)
    return;
  unsigned int father = FatherPos(index);
  while (Compter(BasicHeap[index], BasicHeap[father])) {
    Swap(index, father);
    index = father;
    if (index == 0) {
      return;
    } else {
      father = FatherPos(index);
    }
  }
}

template <typename Type, typename Compare>
void HeapGreater<Type, Compare>::Heapyfy(unsigned int index) {
  if (index >= HeapSize)
    return;
  unsigned int left = LeftKid(index);
  while (left < HeapSize) {
    unsigned int right = RightKid(index);
    unsigned int min =
        (right < HeapSize) && Compter(BasicHeap[right], BasicHeap[left]) ? right
                                                                         : left;
    if (Compter(BasicHeap[min], BasicHeap[index])) {
      Swap(min, index);
      index = min;
      left = LeftKid(index);
    } else {
      break;
    }
  }
}

template <typename Type, typename Cmp> bool HeapGreater<Type, Cmp>::IsEmpty() {
  assert(!(BasicHeap.empty() ^ BackIndex.empty()));
  return BasicHeap.empty();
}

template <typename Type, typename Cmp>
bool HeapGreater<Type, Cmp>::Contains(const Type &node) {
  if (BackIndex.find(node) != BackIndex.end())
    return true;
  return false;
}

template <typename Type, typename Cmp> int HeapGreater<Type, Cmp>::Size() {
  assert(HeapSize == BackIndex.size() && HeapSize == BasicHeap.size());
  return HeapSize;
}

template <typename Type, typename Cmp>
bool HeapGreater<Type, Cmp>::Push(const Type &node) {
  BasicHeap.push_back(node);
  BackIndex[node] = HeapSize;
  HeapInsert(HeapSize++);
  return true;
}

template <typename Type, typename Cmp> void HeapGreater<Type, Cmp>::Pop() {
  if (IsEmpty())
    return;
  Type a = Get();
  Swap(0, HeapSize - 1);
  BasicHeap.pop_back();
  BackIndex.erase(a);
  --HeapSize;
  Heapyfy(0);
}

template <typename Type, typename Cmp> Type HeapGreater<Type, Cmp>::Get() {
  return BasicHeap[0];
}

template <typename Type, typename Cmp> bool HeapGreater<Type, Cmp>::IsValid() {
  if (HeapSize != BasicHeap.size() || HeapSize != BackIndex.size()) {
    return false;
  }
  for (int i = 0; i < HeapSize; ++i) {
    cout << BasicHeap[i] << " ";
    unsigned int left = LeftKid(i);
    unsigned int right = RightKid(i);
    if ((left < HeapSize) && (right < HeapSize)) {
      if (Compter(BasicHeap[i], BasicHeap[left]) &&
          Compter(BasicHeap[i], BasicHeap[right])) {
        continue;
      } else {
        return false;
      }
    } else if (left < HeapSize) {
      if (Compter(BasicHeap[i], BasicHeap[left])) {
        continue;
      } else {
        return false;
      }
    }
    if (BackIndex.find(BasicHeap[i]) == BackIndex.end()) {
      return false;
    }
  }
  cout << endl;
  return true;
}

class IntComp {
public:
  bool operator()(const int &a, const int &b) const { return b < a; }
};

int main(int argc, char *argv[]) {
  int trytimes = 1000;
  for (int kk = 0; kk < trytimes; ++kk) {
    int min = 0, max = 100;
    random_device seed;      // 硬件生成随机数种子
    ranlux48 engine(seed()); // 利用种子生成随机数引擎
    uniform_int_distribution<> distrib(min,
                                       max); // 设置随机数范围，并为均匀分布

    HeapGreater<int, IntComp> a;
    std::set<int> b;
    int len = 100;
    int i = 0;
    while (i < len) {
      int temp = distrib(engine);
      if (b.find(temp) == b.end()) {
        b.insert(temp);
      } else {
        continue;
      }
      a.Push(temp);
      if (!a.IsValid()) {
        cout << "Error" << endl;
      }
      ++i;
    }
    int tmel = a.Size();
    for (int j = 0; j < tmel; ++j) {
      a.Pop();
      if (!a.IsValid()) {
        cout << "Pop Error" << endl;
      }
    }
  }

  return 0;
}
